'''
Ported from original C at
http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html
'''

# assumes that the cell coordinates are integers
# XXX This approach is FLAWED:
#     The cells sampled depend on the direction of the ray check. On a 45-degree
#     ray this means that entirely different cells are checked in each direction.
#     
def line_of_sight_ray(level, source, destination, ignore_creatures, range=None,
        debug=False, target=None):

    if isinstance(source, tuple):
        x0, y0 = source
    else:
        x0, y0 = source.x, source.y
    if isinstance(destination, tuple):
        x1, y1 = destination[0], destination[1]
    else:
        x1, y1 = destination.x, destination.y

    x, y = x0, y0
    dx, dy = abs(x1-x0), abs(y1-y0)

    if x1 > x0:
        x_inc =  1
    else:
        x_inc = -1

    if y1 > y0:
        y_inc =  1
    else:
        y_inc = -1

    n = 1 + dx + dy
    error = dx - dy

    dx *= 2; dy *= 2

    visited = []

    while n > 0:
        if ignore_creatures or (target is not None and target.position == (x, y)):
           cur = level.ground.get_cell(x, y)
        else:
           cur = level.get_cell(x, y)

        if (x, y) != (x0, y0):
            # don't check impassable on the source cell
            if debug: print cur, cur.get('impassable')
            if not cur or cur.get('impassable'): return []

        visited.append(cur)

        if error > 0:
            x += x_inc
            error -= dy
        else:
            y += y_inc
            error += dx
        n -= 1

    return filter(None, visited)

class LineOfSight(object):
    def __init__(self, level, source, destination, ignore_creatures, range=None,
            debug=False, target=None):
        self.quality, self.path = line_of_sight(level, source, destination,
            ignore_creatures, range, debug, target)

    def __nonzero__(self):
        return bool(self.quality)

    def __cmp__(self, other):
        c = cmp(len(self.path), len(other.path))
        if c: return c
        return cmp(self.quality, other.quality)

    def __repr__(self):
        return '<LineOfSight %s %r>'%(self.quality, self.path and [c.position for c in self.path])


def line_of_sight(level, source, destination, ignore_creatures, range=None,
        debug=False, target=None):
    ''' Cheat by testing both directions of our above test.

    Visibility is a rough indication - 1 if both tests pass, .5 if only one does.
    Distance is the length of the first visibility ray that passes.

    If target is supplied then ignore that creture as it's allowed to block LoS :)

    Return LineOfSight(visibility, distance)
    '''
    # XXX this needs to be better
    l = line_of_sight_ray(level, source, destination, ignore_creatures, range, debug, target)
    m = line_of_sight_ray(level, destination, source, ignore_creatures, range, debug, target)
    if l:
        if m:
            return (1, l)
        else:
            return (.5, l)
    elif m:
        return (.5, m)
    return (0, [])

